package Offer.offer2016;
//�ݹ�ʵ��

import domain.ListNode;

public class Test17 {

    public static void main(String[] args) {
        ListNode p1 = new ListNode(2);
        ListNode p2 = new ListNode(3);
        ListNode p3 = new ListNode(5);
        ListNode p4 = new ListNode(7);
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = null;
        ListNode p5 = new ListNode(2);
        ListNode p6 = new ListNode(3);
        ListNode p7 = new ListNode(6);
        ListNode p8 = new ListNode(8);
        p5.next = p6;
        p6.next = p7;
        p7.next = p8;
        p8.next = null;
//		ListNode p = merge(p1,p5);
        ListNode p = MergeLinked.mergeLinked(p4, p8);
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
        }

    }

    public static ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null)
            return head2;
        if (head2 == null)
            return head1;
        ListNode newHead = null;

        if (head1.val <= head2.val) {
            newHead = head1;
            newHead.next = merge(head1.next, head2);
        } else {
            newHead = head2;
            newHead.next = merge(head1, head2.next);
        }
        return newHead;
    }
}

class MergeLinked {
    public static ListNode mergeLinked(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        ListNode mergeList = null;
        ListNode throughMerge = null;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                if (mergeList == null) {
                    throughMerge = mergeList = list1;
                } else {
                    throughMerge.next = list1;
                    throughMerge = throughMerge.next;
                }
                list1 = list1.next;
            } else {
                if (mergeList == null) {
                    throughMerge = mergeList = list2;
                } else {
                    throughMerge.next = list2;
                    throughMerge = throughMerge.next;
                }
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            throughMerge.next = list1;
        }
        if (list2 != null) {
            throughMerge.next = list2;
        }
        return mergeList;
    }
}
